#include"List.h"

//初始化
ListNode* ListNodeInit()
{
	ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (head == NULL)
	{
		printf("malloc failed");
		exit(-1);
	}
	//哨兵位的自循环
	head->next = head;
	head->prev = head;

	return head;
}
//新节点的创建
ListNode* BuyNewNode(ListNodeDataType x)
{
	ListNode* NewNode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (NewNode == NULL)
	{
		printf("malloc failed");
		exit(-1);
	}

	NewNode->data = x;
	NewNode->next = NULL;
	NewNode->prev = NULL;

	return NewNode;
}
//打印链表
void PrintListNode(ListNode* phead)
{
	//可以为空链表，但是得有哨兵位
	assert(phead);
	printf("哨兵位<=>");
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=> ", cur->data);
	}
	printf("\n");
}
//尾插
void PushBack(ListNode* phead, ListNodeDataType x)
{
	assert(phead);
	ListNode* NewNode = BuyNewNode(x);

	ListNode* tail = phead->prev;

	tail->next = NewNode;
	NewNode->prev = tail;

	NewNode->next = phead;
	NewNode->prev = tail;
}
//尾删
void PopBack(ListNode* phead)
{
	//不能没有哨兵位
	//不能只有哨兵位
	assert(phead);
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* tailprev = phead->prev->prev;

	tailprev->next = phead;
	phead->prev = tailprev;

	free(tail);
}

//头插
void PushFront(ListNode* phead, ListNodeDataType x)
{
	assert(phead);
	ListNode* first = phead->next;

	ListNode* NewNode = BuyNewNode(x);
	//新节点与原头结点的循环
	NewNode->next = first;
	first->prev = NewNode;
	//新节点和哨兵位的循环
	phead->next = NewNode;
	NewNode->prev = phead;
}
//头删
void PopFront(ListNode* phead)
{
	//不能没有哨兵位
	//不能只有哨兵位
	assert(phead);
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = phead->next->next;

	phead->next = second;
	second->prev = phead;

	free(first);

}
//查找值为x的节点
ListNode* Findx(ListNode* phead, ListNodeDataType x)
{
	//断言
	assert(phead);
	ListNode* cur = phead->next;
	//从哨兵的下一个节点到哨兵的前一个节点
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
//在pos节点前插入一个值为x的节点
void InSert(ListNode* phead, ListNode* pos, ListNodeDataType x)
{
	assert(pos);
	ListNode* NewNode = BuyNewNode(x);
	ListNode* posprev = pos->prev;

	posprev->next = NewNode;
	NewNode->prev = posprev;

	NewNode->next = pos;
	pos->prev = NewNode;
}
//删除pos节点
void Erase(ListNode* phead, ListNode* pos)
{
	assert(pos);
	ListNode* posprev = pos->prev;
	ListNode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;

	free(pos);


}